using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0309. 最佳买卖股票时机含冷冻期")]
    public class No0309_MaxProfit : AbsBaseTestItem
    {
        /*
        给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

        设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

            你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
            卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
        */
        public override void OnTest()
        {
            Assert.TestExe(MaxProfit, new int[] { 1, 2, 3, 0, 2 }, 3);
            Assert.TestExe(MaxProfit, new int[] { 5, 0, 80, 2, 1 }, 80);

            Assert.TestExe(MaxProfit2, new int[] { 1, 2, 3, 0, 2 }, 3);
            Assert.TestExe(MaxProfit2, new int[] { 5, 0, 80, 2, 1 }, 80);
        }

        /// <summary>
        /// 方法一：动态规划
        /// </summary>
        public int MaxProfit(int[] prices)
        {
            if (prices.Length == 0) return 0;

            int n = prices.Length;
            // f[i][0]: 手上持有股票的最大收益
            // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
            // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
            int[,] f = new int[n, 3];
            f[0, 0] = -prices[0];
            for (int i = 1; i < n; i++)
            {
                f[i, 0] = Math.Max(f[i - 1, 0], f[i - 1, 2] - prices[i]);
                f[i, 1] = f[i - 1, 0] + prices[i];
                f[i, 2] = Math.Max(f[i - 1, 1], f[i - 1, 2]);
            }
            return Math.Max(f[n - 1, 1], f[n - 1, 2]);
        }

        /// <summary>
        /// 方法一：动态规划 优化版本
        /// </summary>
        public int MaxProfit2(int[] prices)
        {
            if (prices.Length == 0) return 0;

            int n = prices.Length;
            // f0: 手上持有股票的最大收益
            // f1: 手上不持有股票，并且处于冷冻期中的累计最大收益
            // f2: 手上不持有股票，并且不在冷冻期中的累计最大收益
            int f0 = -prices[0];
            int f1 = 0;
            int f2 = 0;
            for (int i = 1; i < n; i++)
            {
                int nf0 = Math.Max(f0, f2 - prices[i]);
                int nf1 = f0 + prices[i];
                int nf2 = Math.Max(f1, f2);
                f0 = nf0;
                f1 = nf1;
                f2 = nf2;
            }
            return Math.Max(f1, f2);
        }
    }
}
